Within conventional computer systems, applications are executed by a microprocessor which necessarily uses memory locations for storing data and instructions. The contents of memory are changing over time such that, at different times, a memory location is said to be allocated, i.e., used, or unallocated, i.e., unused. More particularly, allocated memory locations are those locations that contain data or instructions that are referenced by other allocation memory locations during normal program execution.
For example, in modern object oriented computing, an "object" is data that share a particular attribute and occupy a contiguous region of memory. If all objects in a given computer system are permanent, there is no real concern with regard to memory management. That is, the memory space assigned to each object at the start of program execution never changes. However, in most conventional object oriented systems, objects have varying lifetimes that cannot be predicted in advance such that memory locations will transition between allocated and unallocated states. In order to promote the efficient use of memory, unallocated memory locations must be "reclaimed" so that they may be later allocated as required.
"Garbage" is a well-known term in the computer science arts which refers to memory storage locations which contain data that is no longer being used in, e.g., the execution of an application program. Garbage collection is another well-known term of art used in describing automatic techniques for identifying garbage and reclaiming those memory locations for future allocation. By automatically identifying accessible, and therefore potentially in-use data, e.g., objects, garbage collection routines shoulder the error-prone task of memory allocation and deallocation for the computer programmer. In freeing computer programmers from such low-level detail, garbage collection at a minimum can improve the quality of program code, increase programmer productivity, and reduce program development costs.
Of course, the many advantages associated with garbage collection are not "free" in terms of computing resources. Traditional garbage collection techniques such as "stop & copy", "mark & sweep" and "reference counting" are described by, for example, Paul R. Wilson, "Uniprocessor Garbage Collection Techniques", In International Workshop on Memory Management, Springer-Verlag, 1992, and Richard Jones et al., Garbage Collection Algorithms for Automatic Dynamic Memory Management, John Wiley & Sons, 1996. The costs associated with such traditional garbage collection techniques manifest themselves, for example, as combinations of increased memory usage, run-time overheads on data accesses, and disruptive latencies in a program's execution. For example, stop & copy garbage collectors require a substantial amount of additional storage for making copies of live, i.e., allocated, data. This is due to the fact that such collectors periodically copy all reachable objects into a second memory space so the first memory space can be reclaimed in its entirety.
Alternatively, mark & sweep collectors employ a "collector" which synchronizes the launching of markers and sweepers for the purpose of garbage collection. Basically, the marker traverses all memory locations and "marks" those which are presently being used by an application (also alternatively referred to as the "mutator" herein and as wellknown in the garbage collection computing arts). Further, objects which remain unmarked are available for reallocation. The sweeper follows the marker and places the free memory locations, i.e., unmarked objects, in a so called "free-list" from which the memory can be reallocated by the computer system. A disadvantage of mark & sweep garbage collection is that the collector must continually step through the entire set of free and in-use memory objects thereby making the total time required for garbage collection directly proportional to the number of the memory objects in the system.
In order to address the inherent costs of garbage collection techniques as described above, the developers of garbage collection routines have incorporated concurrency in their designs whereby garbage collection occurs contemporaneously with application execution, i.e., mutator execution. More particularly, concurrent garbage collection techniques fall generally into one of two classes: (1) variations on mark & sweep collectors, see, for example, E. W. Dijkstra et al., "On-the-fly garbage collection: An exercise in cooperation", Communications of the ACM, 21(11):966-975, November 1978 (hereinafter referred to as "Dijkstra"), and G. L. Steele, Jr., "Multiprocessing compactifying garbage collection", Communications of the ACM, 18(9):495-508, September 1975; and (2) incremental generational collectors, see, for example, H. G. Baker, "List processing in real time on a serial computer", Communications of the ACM, 21(4):280-294, April 1978, A. W. Appel et al., "Real-time concurrent collection on stock multiprocessors", In Conference on Programming Language Design and Implementation, pp. 11-20, June 1988, and S. Nettles et al., "Replication-based real-time garbage collection", In Conference on Programming Language Design and Implementation, Association for Computing Machinery, June 1993.
Although concurrent garbage collection techniques provide a level of marked improvement over non-concurrent garbage collection, concurrent garbage collectors require substantial synchronization between the application, i.e., mutator, and the garbage collector to ensure data integrity and to avoid interference between the respective activities of the mutator and garbage collector. For example, in Dijkstra, a concurrent mark & sweep garbage collector (hereinafter referred to as "the Dijkstra collector") is described which employs a well-known tricolor abstraction scheme (see, for example, Dijkstra, supra. at pp. 969-972, and Jones et al., supra. at pp. 186-187) to distinguish presently allocated objects from garbage. In particular, conventional tricolor marking employs the following three colors: (1) black--indicates that the object is presently allocated and used; (2) gray--indicates that an object is in a transitional state and is in the process of being retained; and (3) white--indicates objects that are subject to collection, i.e., garbage. For example, the Dijkstra collector at the beginning of the collection cycle uses the tricolor abstraction to color all of the objects in the root set (i.e., the beginning set of objects) the color gray. Depending on their individual allocation status, particular white objects are marked gray by the marker and all children, i.e., descendants attributable to a particular object, of the particular white object are colored gray. After an object's children have been colored gray, the object itself, i.e., the parent, is colored black. As gray objects are generated by Dijkstra's collector these objects are queued for marking. As will be readily understood, objects which retain a white color during the collection cycle are designated as garbage at the end of the marker phase and therefore subject to collection.
At this junction in the operation of Dijkstra's collector (i.e., the end of a collection cycle), the interpretation of the colors white and black, respectively, is reversed from that of the just prior garbage collection cycle. The reversal of the white and black colors occurs, in the Dijkstra collector, at the end of each collection cycle. Significantly, the color gray and the interpretation of gray objects does not change during this transition in the Dijkstra collector and the sweeping phase of this collector must strictly follow the marking phase because of the fact that a white object's color may change (e.g., to gray and later to black) at any point in time during the marking phase. As a result, the Dijkstra collector requires that sweeping always follow marking because it is only at the end of the marking cycle that a determination can be ascertained at to whether certain objects, e.g., white objects, can be reclaimed as garbage.
Furthermore, in order to effectively utilize the tricolor marking scheme, the Dijkstra collector requires so called "fine-grain synchronization" between the mutator and the collector. More particularly, such fine-grain synchronization is realized through the utilization of a write barrier which prevents the mutator from interfering with the collector during garbage collection. Thus, fine-grain synchronization insures that the mutator and collector do not simultaneously access and alter a common object.
Known garbage collection techniques which eliminate this sequential mark-then-sweep requirement are described, for example, in C. Queinnec et al., "Mark DURING Sweep, rather than Mark THEN Sweep", In Parle, pp. 224-237, 1989 (hereinafter "the Queinnec collector"), and in L. Lamport, "Garbage Collection with Multiple Processes: An Exercise in Parallelism", In Proceedings of the International Conference on Parallel Processing, pp. 50-54, August 1976 (hereinafter "the Lamport collector"). The derivation of both the Queinnec collector and the Lamport collector rely significantly on the principles of the above-described Dijkstra collector but depart in one way from Dijkstra's collector by employing five colors to achieve their concurrency. As one might expect the introduction of five colors in these collector's color abstraction schemes increases the complexity of these two collectors. However, even more importantly, both the Queinnec collector and Lamport collector incorporate the so called "shade" atomic operation used by the Dijkstra collector. That is, the Queinnec collector and the Lamport collector each require frequent inter-processor synchronization amongst their respective marker and mutator during typical collection operations because either the marker or mutator can modify a color (i.e., any of the five colors in the abstraction) visible to the other. As will be appreciated, such inter-processor synchronization, i.e., fine-grain synchronization, comes at an increase in processing overhead.
More particularly, for example, the Queinnec collector provides for concurrent threads of operation for the mutator, marker and sweeper thereby allowing for marking during sweeping. However, such concurrency comes with a significant atomicity requirement. The notion of atomicity in the garbage collection context means that access to a shared memory variable, i.e., a memory location, is mutually exclusive. That is, if one thread, e.g., the mutator, has access to the variable, another thread, e.g., the marker, must wait until the first thread explicitly relinquishes its rights to the variable. In terms of processing requirements, atomicity is an expensive feature because it requires a first thread to indicate to the other threads when the thread is going to "lock" a variable, and then again when the thread is done and "unlocks" the variable. The Queinnec collector utilizes atomic operations in the performance of mutation, marking and sweeping. For example, when an object in the Queinnec collector is being examined by the marker there is a lock placed on that object which prohibits access by the sweeper and/or mutator. More particularly, this collector requires multiple fine-grain synchronizations within a single mark or sweep step, and further requires that mutator operations occur atomically. Thus, in effect, these atomic operations act similar to that as the previously described write barrier and require a significant amount of processing overhead.
Therefore, a need exists for a garbage collection technique which allows for fill concurrency between mutation, marking and sweeping without the need for fine-grain synchronization or atomicity.